
/**
解题步骤
定义子问题：
原问题是“从全部房子中能偷到的最大金额”，将问题的规模缩小，子问题就是“从 k 个房子中能偷到的最大金额”，用 f(k) 表示。

可以看到，子问题是参数化的，我们定义的子问题中有参数 k。
假设一共有 n 个房子的话，就一共有 n个子问题。

动态规划实际上就是通过求这一堆子问题的解，来求出原问题的解。这要求子问题需要具备两个性质：

原问题要能由子问题表示。
例如这道小偷问题中，k=n 时实际上就是原问题。否则，解了半天子问题还是解不出原问题，那子问题岂不是白解了。

一个子问题的解要能通过其他子问题的解求出。
例如这道小偷问题中，f(k) 可以由 f(k-1)和 f(k-2)求出，具体原理后面会解释。这个性质就是教科书中所说的“最优子结构”。如果定义不出这样的子问题，那么这道题实际上没法用动态规划解。

写出子问题的递推关系：
这一步是求解动态规划问题最关键的一步。然而，这一步也是最无法在代码中体现出来的一步。在做题的时候，最好把这一步的思路用注释的形式写下来。

做动态规划题目不要求快，而要确保无误。否则，写代码五分钟，找 bug 半小时，岂不美哉？

这道题中，偷k间房子有两种偷法，
第一种是偷第k间房子，相应的不能偷k-1间房子，另外还要再前k-2偷到最大金额。
另外一种是不偷第k间房子，在前k-1间房子中偷到最大金额。
这两种方法中偷出金额最大的就是最佳方案。所以有表达式：

 */
//f(k) = max( f(k-1), f(k-2) + H[k])

	//递归， 效率低
	/*
	public int rob(int[] nums) {
        return rob(nums, nums.length);
    }

    public int rob(int[] nums, int n){
        if(n == 0)
            return 0;
        else if(n == 1)
            return nums[0];
        else{
            return max(rob(nums, n-2)+ nums[n-1], rob(nums, n-1));
        }
    }

    public int max(int a, int b){
        return a>b ? a:b;
    }
    */

    //滚动数组
    public int rob(int[] nums){
        if(nums.length == 0)
            return 0;
        if(nums.length == 1)
            return nums[0];
        int p = 0; // f(0)
        int q = nums[0]; // f(1)
        int r = max(p + nums[1], q);

        for(int i=0;i<nums.length-2;i++){
            p = q;
            q = r;
            r = max(p + nums[i+2], q);
        }
        return r;
    }

    public int max(int a, int b){
        return a>b?a:b;
    }
